package bma.common.langutil.concurrent;

import java.util.concurrent.atomic.AtomicReference;

public class LinkedNode<E> extends AtomicReference<LinkedNode<E>> {

	private static final long serialVersionUID = 1L;

	private volatile LinkedNode<E> prev;

	final E element;

	/** Creates a LinkedNode with given contents */
	LinkedNode(E element, LinkedNode<E> next, LinkedNode<E> prev) {
		super(next);
		this.prev = prev;
		this.element = element;
	}

	/** Creates a marker LinkedNode with given successor */
	LinkedNode(LinkedNode<E> next) {
		super(next);
		this.prev = this;
		this.element = null;
	}

	/**
	 * Gets next link (which is actually the value held as atomic reference).
	 */
	private LinkedNode<E> getNext() {
		return get();
	}

	/**
	 * Sets next link
	 * 
	 * @param n
	 *            the next LinkedNode
	 */
	void setNext(LinkedNode<E> n) {
		set(n);
	}

	/**
	 * compareAndSet next link
	 */
	private boolean casNext(LinkedNode<E> cmp, LinkedNode<E> val) {
		return compareAndSet(cmp, val);
	}

	/**
	 * Gets prev link
	 */
	private LinkedNode<E> getPrev() {
		return prev;
	}

	/**
	 * Sets prev link
	 * 
	 * @param b
	 *            the previous LinkedNode
	 */
	void setPrev(LinkedNode<E> b) {
		prev = b;
	}

	/**
	 * Returns true if this is a header, trailer, or marker LinkedNode
	 */
	boolean isSpecial() {
		return element == null;
	}

	/**
	 * Returns true if this is a trailer LinkedNode
	 */
	boolean isTrailer() {
		return getNext() == null;
	}

	/**
	 * Returns true if this is a header LinkedNode
	 */
	boolean isHeader() {
		return getPrev() == null;
	}

	/**
	 * Returns true if this is a marker LinkedNode
	 */
	boolean isMarker() {
		return getPrev() == this;
	}

	/**
	 * Returns true if this LinkedNode is followed by a marker, meaning that it
	 * is deleted.
	 * 
	 * @return true if this LinkedNode is deleted
	 */
	boolean isDeleted() {
		LinkedNode<E> f = getNext();
		return f != null && f.isMarker();
	}

	/**
	 * Returns next LinkedNode, ignoring deletion marker
	 */
	private LinkedNode<E> nextNonmarker() {
		LinkedNode<E> f = getNext();
		return (f == null || !f.isMarker()) ? f : f.getNext();
	}

	/**
	 * Returns the next non-deleted LinkedNode, swinging next pointer around any
	 * encountered deleted nodes, and also patching up successor''s prev link to
	 * point back to this. Returns null if this LinkedNode is trailer so has no
	 * successor.
	 * 
	 * @return successor, or null if no such
	 */
	LinkedNode<E> successor() {
		LinkedNode<E> f = nextNonmarker();
		for (;;) {
			if (f == null)
				return null;
			if (!f.isDeleted()) {
				if (f.getPrev() != this && !isDeleted())
					f.setPrev(this); // relink f's prev
				return f;
			}
			LinkedNode<E> s = f.nextNonmarker();
			if (f == getNext())
				casNext(f, s); // unlink f
			f = s;
		}
	}

	/**
	 * Returns the apparent predecessor of target by searching forward for it
	 * starting at this LinkedNode, patching up pointers while traversing. Used
	 * by predecessor().
	 * 
	 * @return target's predecessor, or null if not found
	 */
	private LinkedNode<E> findPredecessorOf(LinkedNode<E> target) {
		LinkedNode<E> n = this;
		for (;;) {
			LinkedNode<E> f = n.successor();
			if (f == target)
				return n;
			if (f == null)
				return null;
			n = f;
		}
	}

	/**
	 * Returns the previous non-deleted LinkedNode, patching up pointers as
	 * needed. Returns null if this LinkedNode is header so has no successor.
	 * May also return null if this LinkedNode is deleted, so doesn't have a
	 * distinct predecessor.
	 * 
	 * @return predecessor or null if not found
	 */
	LinkedNode<E> predecessor() {
		LinkedNode<E> n = this;
		for (;;) {
			LinkedNode<E> b = n.getPrev();
			if (b == null)
				return n.findPredecessorOf(this);
			LinkedNode<E> s = b.getNext();
			if (s == this)
				return b;
			if (s == null || !s.isMarker()) {
				LinkedNode<E> p = b.findPredecessorOf(this);
				if (p != null)
					return p;
			}
			n = b;
		}
	}

	/**
	 * Returns the next LinkedNode containing a nondeleted user element. Use for
	 * forward list traversal.
	 * 
	 * @return successor, or null if no such
	 */
	LinkedNode<E> forward() {
		LinkedNode<E> f = successor();
		return (f == null || f.isSpecial()) ? null : f;
	}

	/**
	 * Returns previous LinkedNode containing a nondeleted user element, if
	 * possible. Use for backward list traversal, but beware that if this method
	 * is called from a deleted LinkedNode, it might not be able to determine a
	 * usable predecessor.
	 * 
	 * @return predecessor, or null if no such could be found
	 */
	LinkedNode<E> back() {
		LinkedNode<E> f = predecessor();
		return (f == null || f.isSpecial()) ? null : f;
	}

	/**
	 * Tries to insert a LinkedNode holding element as successor, failing if
	 * this LinkedNode is deleted.
	 * 
	 * @param element
	 *            the element
	 * @return the new LinkedNode, or null on failure.
	 */
	LinkedNode<E> append(E element) {
		for (;;) {
			LinkedNode<E> f = getNext();
			if (f == null || f.isMarker())
				return null;
			LinkedNode<E> x = new LinkedNode<E>(element, f, this);
			if (casNext(f, x)) {
				f.setPrev(x); // optimistically link
				return x;
			}
		}
	}

	/**
	 * Tries to insert a LinkedNode holding element as predecessor, failing if
	 * no live predecessor can be found to link to.
	 * 
	 * @param element
	 *            the element
	 * @return the new LinkedNode, or null on failure.
	 */
	LinkedNode<E> prepend(E element) {
		for (;;) {
			LinkedNode<E> b = predecessor();
			if (b == null)
				return null;
			LinkedNode<E> x = new LinkedNode<E>(element, this, b);
			if (b.casNext(this, x)) {
				setPrev(x); // optimistically link
				return x;
			}
		}
	}

	/**
	 * Tries to mark this LinkedNode as deleted, failing if already deleted or
	 * if this LinkedNode is header or trailer
	 * 
	 * @return true if successful
	 */
	boolean delete() {
		LinkedNode<E> b = getPrev();
		LinkedNode<E> f = getNext();
		if (b != null && f != null && !f.isMarker()
				&& casNext(f, new LinkedNode<E>(f))) {
			if (b.casNext(this, f))
				f.setPrev(b);
			return true;
		}
		return false;
	}

	/**
	 * Tries to insert a LinkedNode holding element to replace this LinkedNode.
	 * failing if already deleted.
	 * 
	 * @param newElement
	 *            the new element
	 * @return the new LinkedNode, or null on failure.
	 */
	LinkedNode<E> replace(E newElement) {
		for (;;) {
			LinkedNode<E> b = getPrev();
			LinkedNode<E> f = getNext();
			if (b == null || f == null || f.isMarker())
				return null;
			LinkedNode<E> x = new LinkedNode<E>(newElement, f, b);
			if (casNext(f, new LinkedNode<E>(x))) {
				b.successor(); // to relink b
				x.successor(); // to relink f
				return x;
			}
		}
	}
}